/*	--- 使用Stack ---

------------------

栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。

什么是LIFO呢？我们先回顾一下Queue的特点FIFO：


          ────────────────────────
  (\(\      (\(\    (\(\    (\(\      (\(\
 (='.') ─> (='.')  (='.')  (='.') ─> (='.')
O(_")")   O(_")") O(_")") O(_")")   O(_")")
          ────────────────────────


所谓FIFO，是最先进队列的元素一定最早出队列，而LIFO是最后进Stack的元素一定最早出Stack。如何做到这一点呢？只需要把队列的一端封死：

           ───────────────────────────────┐
  (\(\       (\(\    (\(\    (\(\    (\(\ │
 (='.') <─> (='.')  (='.')  (='.')  (='.')│
O(_")")    O(_")") O(_")") O(_")") O(_")")│
           ───────────────────────────────┘


因此，Stack是这样一种数据结构：只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）来：


	想象一个垃圾桶 


Stack只有入栈和出栈的操作：

	· 把元素压栈：push(E)；
	· 把栈顶的元素“弹出”：pop(E)；
	· 取栈顶元素但不弹出：peek(E)。


在Java中，我们用Deque可以实现Stack的功能：

	· 把元素压栈：push(E)/addFirst(E)；
	· 把栈顶的元素“弹出”：pop(E)/removeFirst()；
	· 取栈顶元素但不弹出：peek(E)/peekFirst()。


为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。

当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。


-------------------------

# Stack的作用

Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。例如：	*/
static void main(String[] args) {
	foo(123);
}

static String foo(x) {
	return "F-" + bar(x + 1);
}

static int bar(int x) {
	return x << 2;
}


/*
层次： n个层级的参数传入(压栈push) -> 方法调用(出栈pop) -> 方法返回值(压栈push)

JVM会创建方法调用栈，每调用一个方法时，先将参数压栈，然后执行对应的方法；当方法返回时，返回值压栈，调用方法通过出栈操作获得方法返回值。

因为方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发StackOverflowError：
*/

//测试无限递归调用
public class Main {
	public static void main(String[] args) {
		increase(1);
	}

	static int increase(int x) {
		return increase(x) + 1;
	}
}


/*
我们再来看一个Stack的用途：对整数进行进制的转换就可以利用栈。

例如，我们要把一个int整数12500转换为十六进制表示的字符串，如何实现这个功能？

首先我们准备一个空栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│   │
└───┘

然后计算12500÷16=781…4，余数是4，把余数4压栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│ 4 │
└───┘

然后计算781÷16=48…13，余数是13，13的十六进制用字母D表示，把余数D压栈：

│   │
│   │
│   │
│   │
│   │
│ D │
│   │
│ 4 │
└───┘

然后计算48÷16=3…0，余数是0，把余数0压栈：

│   │
│   │
│   │
│ 0 │
│   │
│ D │
│   │
│ 4 │
└───┘

最后计算3÷16=0…3，余数是3，把余数3压栈：

│   │
│ 3 │
│   │
│ 0 │
│   │
│ D │
│   │
│ 4 │
└───┘

当商是0的时候，计算结束，我们把栈的所有元素依次弹出，组成字符串30D4，这就是十进制整数12500的十六进制表示的字符串。

--------------------------------

# 计算中缀表达式

在编写程序的时候，我们使用的带括号的数学表达式实际上是中缀表达式，即运算符在中间，例如：1 + 2 * (9 - 5)。

但是计算机执行表达式的时候，它并不能直接计算中缀表达式，而是通过编译器把中缀表达式转换为后缀表达式，例如：1 2 9 5 - * +。

这个编译过程就会用到栈。我们先跳过编译这一步（涉及运算优先级，代码比较复杂），看看如何通过栈计算后缀表达式。

计算后缀表达式不考虑优先级，直接从左到右依次计算，因此计算起来简单。首先准备一个空的栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│   │
└───┘

然后我们依次扫描后缀表达式1 2 9 5 - * +，遇到数字1，就直接扔到栈里：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│ 1 │
└───┘

紧接着，遇到数字2，9，5，也扔到栈里：

│   │
│ 5 │
│   │
│ 9 │
│   │
│ 2 │
│   │
│ 1 │
└───┘

接下来遇到-号时，弹出栈顶的两个元素，并计算9-5=4，把结果4压栈：

│   │
│   │
│   │
│ 4 │
│   │
│ 2 │
│   │
│ 1 │
└───┘

接下来遇到*号时，弹出栈顶的两个元素，并计算2*4=8，把结果8压栈：

│   │
│   │
│   │
│   │
│   │
│ 8 │
│   │
│ 1 │
└───┘

接下来遇到+号时，弹出栈顶的两个元素，并计算1+8=9，把结果9压栈：

│   │
│   │
│   │
│   │
│   │
│   │
│   │
│ 9 │
└───┘

扫描结束后，没有更多的计算了，弹出栈的唯一一个元素，得到计算结果9。


*/


/*  --- 练习 ---

请利用Stack把一个给定的整数转换为十六进制：	*/
import java.util.*;

public class Main {
	public static void main(String[] args) {
		String hex = toHex(12500);

		if (hex.equalsIgnoreCase("30D4")) {
			System.out.println("测试通过");
		} else {
			System.out.println("测试失败");
		}
	}

	static String toHex(int n) {
		// TODO:

		//方法1
		Deque<String> deque = new LinkedList<>();

		while (n / 16 != 0) { // 判断下一次是否为0
			deque.push(Integer.toHexString(n % 16));
			n = n / 16;

			if (n / 16 == 0) { // 最后一次收尾的判断
				deque.push(Integer.toHexString(n % 16));
			}
		}

		StringBuilder sb = new StringBuilder();

		for (String dqString : deque) {
			sb.append(dqString);
		}

		return sb.toString();



		//方法2
		Stack<String> stack = new Stack<>();

		int remainder;

		for ( ; n>0 ; ) {
			remainder = n % 16 ;
			n = n / 16;

			stack.push(remainder < 10 ? String.format("%d", remainder) : String.format("%c", 55 + remainder));
		}

		String output = "";

		for ( ; !stack.empty(); output += stack.pop());

		return output;
	}


	//方法3 (最简洁)
	static String toHex(int n) {
		String alpha = "0123456789ABCDEF";

		if (n < 16) {
			return String.valueOf(alpha.charAt(n));
		}

		return toHex(n/16) + String.valueOf(alpha.charAt(n % 16));
	}
}




/* --- 进阶练习 --- 

请利用Stack把字符串中缀表达式编译为后缀表达式，然后再利用栈执行后缀表达式获得计算结果：	
(高难度练习)
*/
import java.util.*;

public class Main {
	public static void main(String[] args) {
		String exp = "1 + 2 * (9 - 5)";
		SuffixExpression se = compile(exp); // SuffixExpression 后缀表达式
			// compile就是我们要改写的Method
		int result = se.execute();

		System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
	}

	static SuffixExpression compile(String exp) {
		// TODO:

		//运算符优先级
		Map<String, Integer> map = new HashMap<>();

		map.put("+", 1);
		map.put("-", 1);
		map.put("*", 2);
		map.put("/", 2);
		map.put("(", 0); //优先级最高
		map.put(")", 3);

		//后缀表达式
		StringBuilder sb = new StringBuilder();

		//临时运算符栈
		Deque<Character> stackChar = new LinkedList<>();

		//把String -> char[]
		char[] chars = exp.toCharArray();


		/**
		    * 中缀表达式转后缀表达式的方法：
		         * 1.遇到操作数：直接输出（添加到后缀表达式中）
		         * 2.栈为空时，遇到运算符，直接入栈
		         * 3.遇到左括号：将其入栈
		         * 4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
		         * 5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素【栈内的栈顶运算符>=遇到的运算符，就弹出】，然后将该运算符入栈
		         * 6.最终将栈中的元素依次出栈，输出。
		*/

		//遍历
		for (int i = 0; i < chars.length; i++) {
			//跳过空白字符
			if (chars[i] == ' ') {
				continue;
			}

			// 1
			if (Character.isDigit(chars[i])) {

				StringBuilder sbi = new StringBuilder();

				while (Character.isDigit(chars[i] || chars[i] == '.')) {
					sbi.append(chars[i]);
					i++;
				}

				sb.append(Double.parseDouble(sbi.toString()) + " " );
				i--;
			}

			// x,y
			if (chars[i] == 'x' || chars[i] == 'y') {
				sb.append(chars[i] + " ");
				continue;
			}

			//2,3
			if (stackChar.isEmpty() || chars[i] == '(') {
				stackChar.push(chars[i]); // 放入Deque<Character> stackChar
				continue;
			}

			//4
			if (chars[i] == ')') { // 放入Deque<Character> stackChar
				while (!stackChar.isEmpty() && stackChar.peek() != '(') {
					sb.append(stackChar.pop() + " ");
				}

				if (stackChar.peek() == '(') {
					stackChar.pop();
				}

				continue;
			}

			//5
			while (!stackChar.isEmpty() && map.get(chars[i] + "") <= map.get(stackChar.peek() + "")) {
				sb.append(stackChar.pop() + " ");

				stackChar.push(chars[i]);
			} 

			//6
			while (!stackChar.isEmpty()) {
				sb.append(stackChar.pop() + " ");
			}
			System.out.println(sb.toString());

			return new SuffixExpression(sb.toString());
		}

		return new SuffixExpression();
	
}

class SuffixExpression {
	int execute() {
		// TODO:
		private String str;

		public SuffixExpression(String str) {
			this.str = str;
		}

		//利用Stack执行‘后缀表达式’获取计算结果
		double execute(Map<String, Integer> env) {
			//替换变量后需要重新赋值回后缀表达式字符串，只调用replace并不会改变原后缀表达式
			this.str = this.replace("x", env.get("x").doubleValue() + "");
			this.str = this.str.replace("y", env.get("y").doubleValue() + "");

			//运算时存数值的临时栈
	        Deque<Double> stack = new LinkedList<>();

	        char[] chars = this.str.toCharArray();

	        for (int i = 0; i < chars.length; i++) {
	            //跳过空白字符
	            if (chars[i] == ' ') {
	                continue;
	            }

	            //数值压栈
	            if (Character.isDigit(chars[i])) {
	                StringBuilder sbi=new StringBuilder();
	                while (Character.isDigit(chars[i])||chars[i]=='.'){
	                    sbi.append(chars[i]);
	                    i++;
	                }
	                
	                stack.push(Double.parseDouble(sbi.toString()));
	                i--;

	                continue;
	            }

	            //读取两个运算数，注意顺序
	            double b = stack.pop();
	            double a = stack.pop();
	            //根据运算符运算，把结果压栈
	            switch (chars[i]) {
	                case '+':
	                    stack.push(a + b);
	                    break;
	                case '-':
	                    stack.push(a - b);
	                    break;
	                case '*':
	                    stack.push(a * b);
	                    break;
	                case '/':
	                    stack.push(a*1.0 / b);
	                    break;
	                default:
	                    break;
	            }
	        }

	        return stack.pop();

			}

		return 0;
	}
}


// 方法2


/* --- 进阶练习2 ---

请把带变量的中缀表达式编译为后缀表达式，执行后缀表达式时，传入变量的值并获得计算结果：	
(超高难度)
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String exp = "x + 2 * (y - 5)";

        SuffixExpression se = compile(exp); // compile是要写的方法

        Map<String, Integer> env = Map.of("x", 1, "y", 9);

        int result = se.execute(env);
        
        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String exp) {
        // TODO:
    	Deque<Character> s1 = new ArrayDeque<>(); //存放Operator
    	Deque<Character> s2 = new ArrayDeque<>(); //存放Character

    	for (char ch : exp.toCharArray()) {
    		
    		if (Decider.isNumber(ch)) { //判断是否有效字符
    			s2.push(ch); // 放入Stack s2
    		} 
    		else if (Decider.isOperator(ch)) {
    			while (true) {
    				if (s1.isEmpty() || s1.peek() == '(') {
    					s1.push(ch); // ch可能是  + - * / ( ) 这6个
    					break;
    				} else if (Decider.comparePri(ch, s1.peek())) {
    					s1.push(ch);
    					break;
    				} else {
    					s2.push(s1.pop());
    				}
    			}
    		} 
    		else if (ch == '(') {
    			s1.push(ch);
    		} 
    		else if (ch == ')') {
    			while (true) {
    				if (s1.peek() == '(') {
    					s1.pop();
    					break;
    				} else {
    					s2.push(s1.pop());
    				}
    			}
    		}

    	}

    	while (!s1.isEmpty()) {
    		s2.push(s1.pop());
    	}

    	char[] expArray = new char[s2.size()];

    	for (int i = expArray.length - 1; !s2.isEmpty(); i--) {
    		expArray[i] = s2.pop();
    	}

        return new SuffixExpression(expArray);
    }
}

class SuffixExpression {
	private char[] expArray; // 我加的

	public SuffixExpression(char[] expArray) {
		this.expArray = expArray;
	}

    int execute(Map<String, Integer> env) {
        // TODO:
    	Deque<Integer> stack = new ArrayDeque<>();

    	for (char ch : expArray) {

	    	if (Decider.isConstant(ch)) {
	    		stack.push(ch - 48);
	    	} else if (Decider.isVariable(ch)) {
	    		String key = new StringBuilder().append(ch).toString();
	    		stack.push(env.get(key));
	    	} else if (Decider.isOperator(ch)) {
	    		int top = stack.pop();
	    		int subtop = stack.pop();

	    		stack.push(calc(subtop, ch, top));
	    	}
   		}

   		if (stack.size() == 1) {
   			return stack.pop();
   		}

   		return 0;
   	}
    
}


private Integer calc(int e1, char operator, int e2) {
	if (operator == '+') {
		return e1 + e2;
	} else if (operator == '-') {
		return e1 - e2;
	} else if (operator == '*') {
		return e1 * e2;
	} else if (operator == '/') {
		return e1 / e2;
	}

	return null;
}

class Decider { 
	public static boolean isConstant(char ch) {
		return (ch > '0' && ch < '9');
	}

	public static boolean isVariable(char ch) {
		return (ch > 'a' && ch < 'z');
	}

	public static boolean isNumber(char ch) {
		return (isConstant(ch) || isVariable(ch));
	}

	public static boolean isOperator(char ch) {
		return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
	}

	public static boolean comparePri(char op1, char op2) {
		if (op1 == '*' || op1 == '/') {
			return (op2 == '+' || op2 == '-');
		}

		return false;
	}
}


/* --- 使用Stack の 小结 ---


1.栈（Stack）是一种后进先出（LIFO）的数据结构，操作栈的元素的方法有：

	· 把元素压栈：push(E)；
	· 把栈顶的元素“弹出”：pop(E)；
	· 取栈顶元素但不弹出：peek(E)。

2.在Java中，我们用Deque可以实现Stack的功能，注意只调用push()/pop()/peek()方法，避免调用Deque的其他方法。

3.最后，不要使用遗留类Stack。


4.可以使用堆栈将中缀表达式转化为后缀表达式，堆栈中要保存的是运算符。步骤：
从头到尾读取中缀表达式的每一个对象，对不同对象按不同的情况处理，共有6种情况：

	1. 如果遇到空格则认为是分隔符，无须处理/不处理；

	2. 若遇到运算数(变量/常量), 直接输出；

	3. 若是左括号'('，则将其压入至堆栈中 Stack.push('(')；

	4. 若遇到的是右括号')'，表明'括号()'内的中缀表达式已经扫描完毕，将栈顶Stack.peak()的运算符Operator弹出Stack.pop()并输出，直到遇到左括号(后,左括号'('也出栈Stack.pop()，但不输出)；

	5. 若遇到的是运算符Operator，若该运算符Operator的优先级Map.put('Operator',优先值)大于 > 栈顶运算符Stack_Operator的优先级Operator_Priority，则把它压栈Stack.push(Operator)；若该运算符的优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出，再比较新的栈顶运算符，按同样的处理方法，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；

	6. 若中缀表达式中的各个对象处理完毕，则把堆栈中存留的运算符一并输出。


5. 也可以使用堆栈进行后缀表达式计算，堆栈中要保存的是运算数。
从头到尾读取后缀表达式的每一个对象，对不同对象按不同的情况处理，共有3中情况：

	1. 当读入的是一个运算数(Variable/Value)时，把它压入栈Stack.push()中；

	2. 当读入的是一个运算符(Operator)时，就从堆栈Stack中弹出Stack.pop()适当数量的运算数(Variable/Value)并进行计算，计算结果再压回到栈中；

	3. 处理完整个后缀表达式后，堆栈顶上的元素就是表达式的结果值。

*/










